#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

#define MAX 1000
int A[MAX][MAX]; // 图的邻接矩阵
int n;           // 动物数量
int m;           // 能够互相通信的动物对数
int k;           // 查询（通讯）的数量
int sno, eno;    // 想要通讯的双方
int visited[MAX];

struct Node
{
    int vno;    // vertex number
    int length; // 长度（翻译个数）
};

int bfs(int sno, int eno)
{
    if (sno == eno)
        return 0;
    Node e, e1;
    queue<Node> Q;
    e.vno = sno;
    e.length = 0;
    Q.push(e);
    visited[sno] = 1;
    while (!Q.empty())
    {
        e = Q.front();
        Q.pop();
        if (e.vno == eno)
            return e.length - 1;
        for (int i = 0; i < n; i++)
        {
            if (A[e.vno][i] != 0)
            {
                if (visited[i] == 0)
                {
                    e1.vno = i;
                    e1.length = e.length + 1;
                    Q.push(e1);
                    visited[i] = 1;
                }
            }
        }
    }
}
int main()
{
    while (true)
    {
        cout << "请输入动物数量和可互相通信对数：n、m：\n";
        cin >> n >> m;
        int a, b;
        memset(A, 0, sizeof(A));
        cout << "请输入可以互相通信的" << m << "对动物：\n";
        for (int i = 0; i < m; i++)
        {
            cin >> a >> b;
            A[a][b] = 1;
            A[b][a] = 1;
        }
        cout << "请输入想要通信的数量：k=";
        cin >> k;
        for (int i = 0; i < k; i++)
        {
            memset(visited, 0, sizeof(visited));
            cout << "\n第" << i + 1 << "对想要通讯的双方：";
            cin >> sno >> eno;
            cout << "它们需要：" << bfs(sno, eno) << "个翻译\n";
        }
        cout << endl;
    }
    return 0;
}
